package h0920;

import java.util.HashMap;

/**
 * @author 不知名帅哥
 * @version 1.0
 * @description 最小覆盖子串
 * @date 2024/9/20 16:11
 */
public class SmallestCoverSubstring {
    public static void main(String[] args) {
        SmallestCoverSubstring s = new SmallestCoverSubstring();
        String str = "a";
        String t = "a";
        System.out.println(s.minWindow(str, t));
    }

    public String minWindow(String s, String t) {
        HashMap<Character, Integer> tCount = new HashMap<>();
        HashMap<Character, Integer> sCount = new HashMap<>();

        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            tCount.put(c, tCount.getOrDefault(c, 0) + 1);
        }
        //t字符串中关键词的种类数量
        int required = tCount.size();
        //当前窗口关键词的种类数量
        int formed = 0;
        int start = 0;
        int end = 0;

        int minLen = Integer.MAX_VALUE;
        int l = 0;
        int r = 0;
        while (end < s.length()) {
            char c = s.charAt(end);
            sCount.put(c, sCount.getOrDefault(c, 0) + 1);
            if (tCount.containsKey(c) && sCount.get(c).intValue() == tCount.get(c).intValue()) {
                formed++;
            }
            while (start <= end && formed == required) {
                c = s.charAt(start);
                if (end - start + 1 < minLen) {
                    minLen = end - start + 1;
                    l = start;
                    r = end;
                }
                sCount.put(c, sCount.get(c) - 1);
                if (tCount.containsKey(c) && sCount.get(c) < tCount.get(c)) {
                    formed--;
                }
                start++;
            }
            end++;
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(l, r + 1);
    }

}
